import java.util.*;

public class Test {
}
class Solution4 {
    List<String> ret = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        StringBuilder a = new StringBuilder(s);
        dfs(a,0,0);
        return ret;
    }
    private void dfs(StringBuilder s, int index, int k){
        if(k == 3){
            if(s.length()==index) return;//第四段为空
            if(s.charAt(index) == '0' && index+1 < s.length()) return;//第四段的值开始为0
            if(s.length()-index > 3) return;//第四段的值超过int
            int b = Integer.parseInt(s.substring(index));
            if(b>=0 && b<=255){
                ret.add(s.toString());
                return;
            }
        }
        for(int i=index; i<s.length() && i<index+3; i++){
            if(s.charAt(index) == '0' && i > index) return;//前三段的值开始为0
            int a = Integer.parseInt(s.substring(index,i+1));
            if(a >= 0 && a<=255){
                s.insert(i+1,'.');
                dfs(s,i+2,k+1);
                s.deleteCharAt(i+1);
            }
        }
    }
}
class Solution2 {
    List<List<Integer>> ans = new ArrayList<>();

    private void dfs(int[] nums, int index, List<Integer> ret){
        ans.add(new ArrayList<>(ret));
        if(index >= nums.length) return;
        for(int i=index; i<nums.length; i++){
            ret.add(nums[i]);
            dfs(nums,i+1,ret);
            ret.remove(ret.size()-1);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> ret = new ArrayList<>();
        dfs(nums,0,ret);
        return ans;
    }
}
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    boolean[] res;
    private void dfs(int[] nums,int index, List<Integer> ret){
        ans.add(new ArrayList<>(ret));
        for(int i=index; i<nums.length; i++){
            if(i>0 && nums[i] == nums[i-1] && !res[i-1]){
                continue;
            }
            ret.add(nums[i]);
            res[i] = true;
            dfs(nums,i+1,ret);
            ret.remove(ret.size()-1);
            res[i] = false;
        }
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<Integer> ret = new ArrayList<>();
        Arrays.sort(nums);
        res = new boolean[nums.length];
        dfs(nums,0,ret);
        return ans;
    }
    
}
class Solution7 {
    private List<List<Integer>> ans = new ArrayList<>();
    private void dfs(int[] nums, int index, List<Integer> ret){
        if(ret.size() >= 2){
            ans.add(new ArrayList<>(ret));
        }
        Set<Integer> set = new HashSet<>();//记录树层中出现的数字
        for(int i=index; i<nums.length; i++){
            if(ret.size()!=0 && ret.get(ret.size()-1) > nums[i] || set.contains(nums[i])){//每层递归中不能出现同一个数字 && 要是递增的
                continue;
            }
            set.add(nums[i]);//因为每一层都要有，所以它不需要回溯！！！
            ret.add(nums[i]);
            dfs(nums,i+1,ret);
            ret.remove(ret.size()-1);
        }
    }
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<Integer> ret = new ArrayList<>();
        dfs(nums,0,ret);
        return ans;
    }
}
